package k8.util;

/** A simple list structure that can be modified whilst being iterated. */
public final class LinkedList<T> {

	/** Container to store T instances */
    public static final class Node<T> {
        
    	public T 	item;		// Contents of link
        private Node<T> prev;	// Previous link in list
        private Node<T> next;	// Next link in list
        
        /** Creates a new instance of Node */
        public Node(T item, Node<T> prev, Node<T> next) {
        	this.item = item;
        	this.prev = prev;
        	this.next = next;
        	if ( prev != null ) prev.next = this;
        	if ( next != null ) next.prev = this;
        }
        
    }

    private Node<T> first;
    private Node<T> last;
    private int length;
    
    /** Creates a new instance of LinkedList */
    public LinkedList() {
    	first = last = null;
    	length = 0;
    }
    
    /** Gets the number of items in the list */
    public int length() {
    	return length;
    }
    
    /** Prepends T before the specified Node of the list */
    public Node<T> prepend(Node<T> node, T item) {
    	length++;
    	
    	// Is this to be the first contents of the list?
    	if ( first == null ) {
    		first = last = new Node<T>(item, null, null);
    		return first;
    	}
    	
    	// Are we prepending to the beginning of the list (i.e. new first node)?
        if ( node == first || node == null ) {
            first.prev = new Node<T>(item, null, first);
            first = first.prev;
            return first;
        }

        // New node is to be inserted between first and last
        node.prev = new Node<T>(item, node.prev, node);
        return node.prev;
    }
    
    /** Prepends T to beginning of the list */
    public Node<T> prepend(T item) {
    	return prepend(null, item);
    }
    
    /** Appends T after the specified Node of the list */
    public Node<T> append(Node<T> node, T item) {
    	length++;
    	
    	// Is this to be the first contents of the list?
    	if ( first == null ) {
    		first = last = new Node<T>(item, null, null);
    		return first;
    	}
    	
    	// Are we appending to the end of the list (i.e. new last node)?
        if ( node == last || node == null ) {
            last.next = new Node<T>(item, last, null);
            last = last.next;
            return last;
        }
        
        // New node is to be inserted between first and last
        node.next = new Node<T>(item, node, node.next);
        return node.next;
    }
    
    /** Appends T to end of the list */
    public Node<T> append(T item) {
    	return append(null, item);
    }
    
    /**
     * Removes the specified container Node from the list.
     * 
     * Any references to node, can still use it to access its item, or
     * reinsert it using the prepend/append methods.
     */
    public void remove(Node<T> node) {
    	if ( node == null ) return;
    	if ( node == first ) first = node.next;
		if ( node == last ) last = node.prev;
		if ( node.prev != null ) node.prev.next = node.next;
		if ( node.next != null ) node.next.prev = node.prev;
		node.prev = null;
		node.next = null;
    	length--;
    }
    
    /** Iterates the list */
    public Node<T> next(Node<T> node) {
    	if ( node == null ) return first;
    	return node.next;
    }
    
    /** Returns last node of list */
    public Node<T> last() {
    	return last;
    }
    
}
